import java.util.LinkedList;
import java.util.List;

/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/8/5 11:34
 */
// 课程表
    // 有向图的环检测/拓扑排序
    // https://leetcode.cn/problems/course-schedule/
    // https://labuladong.online/algo/data-structure/topological-sort/#%E7%8E%AF%E6%A3%80%E6%B5%8B%E7%AE%97%E6%B3%95-dfs-%E7%89%88%E6%9C%AC
public class Solution207 {
    // 记录遍历过的节点
    boolean[] visited;
    // 记录一次递归栈中的节点
    boolean[] onPath;
    boolean hasCycle = false;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 构建有向图
        List<Integer>[] graph = buildGraph(numCourses, prerequisites);
        visited = new boolean[numCourses];
        onPath = new boolean[numCourses];
        // 遍历图中节点
        for (int i = 0; i < numCourses; i++) {
            traverse(graph ,i);
        }
        return !hasCycle;
    }

    private void traverse(List<Integer>[] graph, int i) {
        if (onPath[i]) {
            hasCycle = true;
        }
        // 已经访问过或者出现了环
        if (visited[i] || hasCycle) {
            return;
        }
        visited[i] = true;
        onPath[i] = true;
        for (int t : graph[i]) {
            traverse(graph, t);
        }
        onPath[i] = false;
    }

    private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new LinkedList[numCourses];
        // 为列表每一个节点建立链表
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new LinkedList<>();
        }
        for (int[] edge : prerequisites) {
            int from = edge[1], to = edge[0];
            // 添加一条从from到to的有向边
            graph[from].add(to);
        }
        return graph;
    }
}
